Complexity Notation

links: AC2 TOC - Number-Theoretic Algorithms and Hardness Assumptions - Index

---

Different algorithmic complexities

From fast to slow

• $\mathcal{O}(1)$ - Constant time
• $\mathcal{O}(\log n)$ - Logarithmic time
• $\mathcal{O}(\sqrt{n})$ - Square root time
• $\mathcal{O}(n)$ - Linear time
• $\mathcal{O}(n\log n)$ - Linear logarithmic time
• $\mathcal{O}(n^2)$ - Quadratic time
• $\mathcal{O}(n^3)$ - Cubic time
• $\mathcal{O}(n^k)$ - Polynomial time
• $\mathcal{O}(2^n)$ - Exponential time
• $\mathcal{O}(n!)$ - Factorial time
• $\mathcal{O}(n^n)$ - "Crazy" exponential time

From the slides:

Notation

For some function $f(n)$

• Big O notation: $\mathcal{O}(f(n))$ - Upper bound. Worst case scenario. (Less or equal)
• Little o notation: $\mathcal{o}(f(n))$ - Upper bound. Worst case scenario. (Strictly less)
• Big Omega notation: $\mathrm{\Omega }(f(n))$ - Lower bound. Best case scenario. (Greater or equal)
• Little omega notation: $\omega (f(n))$ - Lower bound. Best case scenario. (Strictly greater)
• Big Theta notation: $\mathrm{\Theta }(f(n))$ - Equal. Average case scenario.

Master Theorem

To analyse recursive function we need the Master Theorem.

Decrease (R1-2) the problem size by $k$:

$$T(n)=\{\begin{array}{ll}c& \text{if }n=d\\ q\times T(n-k)+f(n)& \text{if }n>d\end{array}$$

Divide (D1-4) the problem size by $r$:

$$T(n)=\{\begin{array}{ll}c& \text{if }n=d\\ q\times T(n/r)+f(n)& \text{if }n>d\end{array}$$

---

links: AC2 TOC - Number-Theoretic Algorithms and Hardness Assumptions - Index